/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._95;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
 * <p>
 * 示例:
 * <p>
 * 输入: 3
 * 输出:
 * [
 *   [1,null,3,2],
 *   [3,2,null,1],
 *   [3,1,null,null,2],
 *   [2,1,3],
 *   [1,null,2,null,3]
 * ]
 * 解释:
 * 以上的输出对应以下 5 种不同结构的二叉搜索树：
 * <p>
 * 1         3     3      2      1
 * \       /     /      / \      \
 * 3     2     1      1   3      2
 * /     /       \                 \
 * 2     1         2                 3
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._95
 * @ClassName: UniqueBinarySearchTreesII
 * @Author: linyaonan
 * @Date: 2020/1/21 10:54
 */
public class UniqueBinarySearchTreesII {
    List<TreeNode> result;

    public List<TreeNode> generateTrees(int n) {
//        for (int i = 1; i <= n; i++) {
//            TreeNode head = new TreeNode(i);
//            result.add(buildTree(head, 1, n, ))
//        }
        return null;
    }

    private TreeNode buildTree(TreeNode head, int lStart, int lEnd, int rStart, int rEnd) {
        if (lStart == lEnd) {
            head.left = new TreeNode(lStart);
            return head;
        }
        if (rStart == rEnd) {
            head.right = new TreeNode(rStart);
            return head;
        }

        for (int i = lStart; i <= lEnd; i++) {
            TreeNode p = new TreeNode(i);
            head.left = buildTree(p, i, lEnd, rStart, rEnd);
        }
        for (int i = rStart; i <= rEnd; i++) {
            TreeNode p = new TreeNode(i);
            head.right = buildTree(p, i, lEnd, rStart, rEnd);
        }
        return head;
    }
}
